package com.huawei.M01.iterator.M25;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 1187. 使数组严格递增
 *
 * @author zhiwu
 */
public class MakingArrayIncreasing {
    static final int INF = Integer.MAX_VALUE;

    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        // 获取数组的长度
        int n = arr1.length;
        List<Integer> collect = Arrays.stream(arr2)
                .sorted()
                .distinct()
                .boxed()
                .collect(Collectors.toList());
        // 使用动态规划来解决问题，dp[i][j]，表示数组前i个元素经过j次替换后末尾的最小值
        int m = collect.size();
        int[][] dp = new int[n + 1][Math.min(n, m) + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], INF);
        }
        // 起始最小值
        dp[0][0] = -1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= Math.min(n, m); j++) {
                if (arr1[i - 1] > dp[i - 1][j]) {
                    dp[i][j] = arr1[i - 1];
                }
                if (j > 0 && dp[i - 1][j - 1] != INF) {
                    // 获取严格大于dp[i -1][j - 1]的数的索引
                    int index = binarySearch(collect, dp[i - 1][j - 1], j - 1);
                    if (index != collect.size()) {
                        dp[i][j] = Math.min(dp[i][j], collect.get(index));
                    }
                }
                if (n == i && dp[i][j] != INF) {
                    return j;
                }
            }
        }
        return -1;
    }

    private int binarySearch(List<Integer> collect, int value, int low) {
        int right = collect.size();

        while (low < right) {
            int mid = low + (right - low) / 2;
            if (collect.get(mid) > value) {
                right = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        System.out.println(new MakingArrayIncreasing().makeArrayIncreasing(new int[]{31, 18, 1, 12, 23, 14, 25, 4, 17, 18, 29, 28, 35, 34, 19, 8, 25, 6, 35}, new int[]{13, 10, 25, 18, 3, 8, 37, 20, 23, 12, 9, 36, 17, 22, 29, 6, 1, 12, 37, 6, 3, 14, 37, 2}));
    }
}
